package leetcode_core.leetcode_1;

public class Trap {
    public int trap(int[] height) {
        if(height.length == 0){
            return 0;
        }
        int n = height.length;
        int ans = 0;
        int left = 0;
        int right =n-1;
        int lMax = height[0];//lMax是height[0...left]中最高柱子的高度
        int rMax=height[n-1];//rMax是height[right...n-1]的最高柱子的高度
        while (left<=right){
            lMax = Math.max(lMax,height[left]);
            rMax = Math.max(rMax,height[right]);
            //ans += Math.min(lMax,rMax)-height[i]
            if(lMax < rMax){
                ans += lMax- height[left];
                left++;
            }else{
                ans += rMax - height[right];
                right--;
            }
        }
        return ans;
    }
}
